package Algorithm.Dp;

import javax.swing.tree.TreeNode;
//https://leetcode-cn.com/problems/house-robber-iii/
//打家劫舍 III
public class Leetcode337_notice_house_robber_iii {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public int rob(TreeNode root) {
            int[] r = afterOrder(root);

            return Math.max(r[0],r[1]);
        }

        public int[] afterOrder(TreeNode root){
            if(null == root){
                return new int[]{0,0};
            }

            int[] left = afterOrder(root.left);
            int[] right = afterOrder(root.right);

            int[] result = new int[2];

            //0 表示选择当前节点
            result[0] = left[1] + right[1] + root.val;

            //1 表示不选择当前节点，此时的最大值有多种可能，都需要判断一回
            int max = Math.max(left[0]+right[0],left[0]+right[1]);
            max = Math.max(max,left[1]+right[1]);
            max = Math.max(max,left[1]+right[0]);
            result[1] = max;

            return result;
        }
    }
}
